home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / modprolg / mod-prol.lha / Prolog / Examples / lib_binary_tree.mod < prev    next >
Text File  |  1992-05-21  |  927b  |  34 lines
  1. signature lib_binary_tree_sig =
  2.   sig
  3.     pred new/1 and insert/3 and preorder/2 and inorder/2 and postorder/2.
  4.   end.
  5.  
  6. structure lib_binary_tree/lib_binary_tree_sig =
  7.   struct
  8.     fun tip/0 and node/3.
  9.     new(tip).
  10.     insert(X,node(Y,L,R),node(Y,NewL,R)) :-
  11.         X < Y, !,
  12.         insert(X,L,NewL).
  13.     insert(X,node(Y,L,R),node(Y,L,NewR)) :-
  14.         insert(X,R,NewR).
  15.     insert(X,tip,node(X,tip,tip)).
  16.     insert(X,node(X,L,R),node(X,L,R)).
  17.     preorder(tip,[]).
  18.     preorder(node(X,L,R),List) :-
  19.         preorder(L,PartL),
  20.         preorder(R,PartR),
  21.         append([X|PartL],PartR,List).
  22.     inorder(tip,[]).
  23.     inorder(node(X,L,R),List) :-
  24.         inorder(L,PartL),
  25.         inorder(R,PartR),
  26.         append(PartL,[X|PartR],List).
  27.     postorder(tip,[]).
  28.     postorder(node(X,L,R),List) :-
  29.         postorder(L,PartL),
  30.         postorder(R,PartR),
  31.         append(PartR,PartL,Part),
  32.         append(Part,[X],List).
  33.   end.
  34.